from matplotlib import pyplot as plt
import matplotlib.patches as mpatches

import numpy as np

# Affichage de la table
def AfficheTable(P, objets, C):
    n = len(objets)

    # Créer une matrice RGB (n+1, C+1, 3)
    mat = np.zeros((n+1, C+1, 3))

    for i in range(n+1):
        for s in range(C+1):
            if (i, s) in P:
                mat[i][s] = [0.2, 0.7, 0.3]  # Vert
            else:
                mat[i][s] = [0.85, 0.85, 0.85]  # Gris clair

    plt.close('all')
    fig, ax = plt.subplots()
    ax.imshow(mat)

    # Afficher les valeurs dans chaque case
    for i in range(n+1):
        for s in range(C+1):
            if (i, s) in P:
                valeur = P[(i, s)]
                ax.text(s, i, str(int(valeur)), ha='center', va='center',
                        color='white', fontsize=8, fontweight='bold')

    ax.set_xticks(np.arange(-0.5, C+1, 1), minor=True)
    ax.set_yticks(np.arange(-0.5, n+1, 1), minor=True)
    ax.grid(which='minor', color='black', linewidth=0.5)

    plt.xlabel('Capacité c')
    plt.ylabel('Nombre d\'éléments i')
    plt.title('Table de programmation dynamique')

    plt.show()


#######################################
# Méthode Bottom-Up
#######################################

# Initialisation de la table
def initialiser_table(A, objets, C):
    # Cas où il n'y a pas d'objets dans le sac
    for c in range(C+1):
        A[(0,c)] = 0

    # Cas où la capacité restante est nulle
    for i in range(len(objets)+1):
        A[(i,0)] = 0
    return A

# Remplissage de la table
# (n+1)(C+1) sous-problemes
# O(1) par case
# Complexité : O(nC)
def remplir_table(A, objets, C):
    n = len(objets)

    for i in range(1,n+1):
        for c in range(1,C+1):
            vi, si = objets[i]          # Valeur et poids de l'objet courant

            if si > c:
                A[(i,c)] = A[(i-1,c)]   # Cas n°1 : On ne prend pas l'objet
            else:
                # Cas n°2 : on choisit le max entre prendre l'objet ou pas
                A[(i,c)] = max(A[(i-1,c)], A[(i-1,c-si)] + vi)

    return A

objets = {1:(7,4),2:(5,3),3:(3,2),4:(6,5),5:(4,2)}
C = 10
A = {}

initialiser_table(A,objets,C)
remplir_table(A, objets,C)
AfficheTable(A,objets,C)

##########################################
# Approche top-down
##########################################

# Fonction récursive
# O(nC) problemes distincts
# Plusieurs couts de O(1) (vérification dictionnaire, comparaisons, max, ..)
# à chaque sous-probleme
# Donc complexité temporelle : O(nC) au total

# Pile d'appels récursif : O(n)
# Table : O(nC)
# Donc complexité spatiale totale : O(nC)
def rec_opt_val(i,c):
    # i : nombre d’objets considérés (les i premiers)
    # c : capacité restante

    # Utilise la mémoïsation
    if (i,c) in A:
        return A[(i,c)]

    # Cas de base quand i = 0 ou c = 0: A[(0, c)] = 0 ; A[(i, 0)] = 0
    if i == 0 or c == 0:
        A[(i,c)] = 0
        return A[(i,c)]

    # Récursion cas n°1 : on ne prend pas l’objet i
    S1 = rec_opt_val(i-1,c)

    # Si s[i] > c alors retourne la solution S1
    vi, si = objets[i]               # Valeur et poids de l'objet i

    if si > c:
        A[(i,c)] = S1
        return S1

    # Cas n°2 : on prend l’objet i
    S2 = rec_opt_val(i - 1, c - si) + vi

    # Sauvegarde et retourne la solution optimale
    A[(i,c)] = max(S1,S2)

    return A[(i,c)]

def objet_pris(A,i,c):
    if A[(i,c)] != A[(i-1,c)]:
        return True
    else:
        return False


# n itérations
# Cout en O(1) (consultaiton dictionnaire, comparaison, ..)
# donc O(n) au total
def reconstruire_solution(A,objets,C):
    n = len(objets)
    c = C

    elements = []

    for i in range(n,0,-1):
        vi, si = objets[i]          # Valeur et poids de l'objet courant
        if objet_pris(A,i,c) == True:
            elements.append(i)
            c = c - si

    return elements

objets = {1:(7,4),2:(5,3),3:(3,2),4:(6,5),5:(4,2)}
C = 10
A = {}

rec_opt_val(len(objets),C)
AfficheTable(A,objets,C)
elements = reconstruire_solution(A,objets,C)

# éléments [5,2,1] : 4|2 + 5|3 + 7|4
# Charge totale : 9kg
# Valeur totale : 16
# Il reste 1 kg de libre dans le sac
print(elements)